package lc20240703;

public class LongestPalindromeSubstring {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;
        
        // 单个字符一定是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 填表格
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 3) {
                        dp[i][j] = true; // 两个字符或三个字符的情况
                    } else {
                        dp[i][j] = dp[i + 1][j - 1]; // 状态转移
                    }
                }
                
                // 更新最长回文子串
                if (dp[i][j] && (j - i + 1 > maxLen)) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }

    public static void main(String[] args) {
        LongestPalindromeSubstring solution = new LongestPalindromeSubstring();
        String input = "babad";
        System.out.println("Longest Palindromic Substring: " + solution.longestPalindrome(input));
    }
}
